首页 > 试题广场 >

合唱队

[编程题]合唱队

热度指数：294924 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。

设 $K$ 位同学从左到右依次编号为 1，2…，K ，他们的身高分别为 $T_1,T_2,…,T_K$ ，若存在 $i(1\leq i\leq K)$ 使得 $T_1<T_2<......<T_{i-1}<T_i$ 且 $T_i>T_{i+1}>......>T_K$ ，则称这 $K$ 名同学排成了合唱队形。

通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。

例子：

123 124 125 123 121 是一个合唱队形

123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求

123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等

数据范围： $1 \le n \le 3000 \$

输入描述:

用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高，以空格隔开

输出描述:

最少需要几位同学出列

示例1

输入

8
186 186 150 200 160 130 197 200

输出

说明

由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130

算法知识视频讲解

Python 3

清风19

提供一份python的代码

def judge(N,list_h):

dp=[1]*len(list_h)

list_h_1=list(reversed(list_h))

dp1=[1]*len(list_h)

for i in range(len(list_h)):

temp=1

for j in range(i):

if list_h[j]<list_h[i]:

temp=max(temp,dp[j]+1)

dp[i]=temp

for i in range(len(list_h)):

temp1=1

for j in range(i):

if list_h_1[j]<list_h_1[i]:

temp1=max(temp1,dp1[j]+1)

dp1[i]=temp1

maxCount=1

for i in range(len(list_h)):

num=dp[i]+dp1[len(list_h)-i-1]

maxCount=max(num,maxCount)

return maxCount

if __name__ == '__main__':

N=int(input())

height=input()

h=height.split(' ')

list_h=[0]*len(h)

for i in range(len(h)):

list_h[i]=int(h[i])

c=judge(N,list_h)

print(len(list_h)-c+1)

发表于 2023-12-31 03:30:24 回复(0)

Python 3

恶作剧之神阿蒙

import bisect

def inc_max(s):
    q = []
    dp=[]
    for n in s:
        idx = bisect.bisect_left(q, n)
        dp.append(idx+1)
        if idx == len(q):
            q.append(n)
        else:
            q[idx] = n
    return dp


N = int(input())
s = list(map(int, input().split()))
left_s = inc_max(s)  # 从左至右
right_s = inc_max(s[::-1])[::-1]  # 从右至左
sum_s = [left_s[i] + right_s[i] - 1 for i in range(len(s))]  # 相加并减去重复计算
print(str(N - max(sum_s)))


#总感觉题解中使用二分法很勉强，看的迷迷糊糊的，感觉这样写会比较明白一些

发表于 2023-02-21 18:09:54 回复(0)

Python 3

在喝茶的咸鱼很温柔

n = int(input())
list1 = list(map(int, input().split()))

def LengthOfLis(lt):  # 定义函数找出最长递增子序列长度
    if not lt:
        return 1
    lt2 = lt[::-1]  # 反向找最长递增子序列
    dp = [1 for _ in range(len(lt))]
    dp2 = [1 for _ in range(len(lt))]
    for i in range(1, len(lt)):  # 找左边最长
        for j in range(i):
            if lt[j] < lt[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    for i in range(1, len(lt2)):  # 找右边最长
        for j in range(i):
            if lt2[j] < lt2[i]:
                dp2[i] = max(dp2[i], dp2[j] + 1)
    dp3 = list(map(lambda x, y: x + y, dp2[::-1], dp))  # 左边加右边 为总长度+重复一项
    return dp3

print(n - max(LengthOfLis(list1)) + 1)  # 原长度-（最长+1），再+1为减去的长度

发表于 2022-12-22 15:14:29 回复(0)

Python 3

最喜欢春天的修勾很贪睡

用函数打包就不超时，不打包就超时，谁能告诉我这是为什么

发表于 2022-11-24 19:20:57 回复(0)

Python 3

木有粗面201904101731812

二分arr，本质上是最长上升子序列的变体

# 关键点，不再使用遍历找最大值的方法，直接使用二分法维护一个排好序的数组
# 时间复杂度为O(nlog(n))
import bisect

n = int(input())
nums = list(map(int, input().split()))

def dpHelper(nums):
    n = len(nums)
    arr = [nums[0]]
    dp = [1]*n
    
    for i in range(1,n):
        if nums[i] > arr[-1]:
            arr.append(nums[i])
            dp[i] = len(arr)
        else:
            # 此处使用二分查找，将该nums[i]插入到序列中，同时dp[i]为插入的位置+1
            # 为什么不用insort,因为arr更像是正常查询时得到数组的叠加状态，仅服务于后面的查询
            index = bisect.bisect_left(arr, nums[i]) 
            arr[index] = nums[i]
            dp[i] = index + 1
    return dp

dpleft = dpHelper(nums)
dpright = dpHelper(nums[::-1])[::-1]

res = 0
for i in range(n):
    tres = dpleft[i] + dpright[i] - 1
    if res < tres:
        res =  tres
print(n - res)

发表于 2022-08-31 17:03:22 回复(0)

Python 3

牛客555680711号

# def solution(nums): #基础动态规划，O(n*n) 超时
#     n = len(nums)
#     if n <= 2: return 0
#     dp = [[1,1] for _ in range(n)] #0 上升，1 下降
#     maxL = 1
#     for i in range(1,n):
#         for j in range(i-1,-1,-1):
#             if nums[i] > nums[j]:
#                 dp[i][0] = max(dp[i][0],dp[j][0]+1)
#             elif nums[i] < nums[j]:
#                 dp[i][1] = max(dp[i][1],dp[j][1]+1,dp[j][0]+1)
#         maxL = max(maxL,dp[i][0],dp[i][1])
#     return n-maxL
import bisect #利用二分查找优化，dp含义改变为递增子序列
def ascMax(nums,dp): #O(nlogn)
    dp += [1]
    b = [float('inf') for _ in range(len(nums))]
    #b[i]代表当前长度为i+1的递增子序列中，结尾值最小为b[i]
    b[0] = nums[0]
    for i in range(1,len(nums)):
        pos = bisect.bisect_left(b,nums[i]) #找到使b保持严格升序的插入点
        b[pos] = nums[i] #插入
        dp += [pos+1] #记录以num[i]结尾的最长递增子序列
while True:
    try:
        n = int(input())
        nums = list(map(int,input().split()))
        dp1,dp2 = [], []
        ascMax(nums,dp1) #获得最长递增子序列
        ascMax(nums[::-1],dp2) ##获得最长递减子序列
        dp2 = dp2[::-1]
        maxVal = 1
        for i in range(n):
            maxVal = max(maxVal,dp1[i]+dp2[i]-1) #以nums[i]为最大值的合唱队长度
        print(n - maxVal)
    except:
        break

发表于 2022-08-24 21:31:32 回复(0)

Python 3

小小苏1997

n = int(input())
seq = list(map(int,input().split()))

def lis(sequence):
    dp, sort = [1], []
    for s in sequence:
        if not sort:
            sort.append(s)
        else:
            if sort[-1] < s:
                sort.append(s)
                dp.append(len(sort))
                continue
            i, j = 0, len(sort) - 1
            #二分搜索 sort 中第一个大于等于s的数字并替换
            while i <= j :
                n = (i + j) // 2
                if sort[n] < s:
                    i = n + 1
                elif sort[n] > s:
                    j = n - 1
                else:
                    i = n 
                    break
            sort[i] = s
            # i + 1 即为 以s结尾的最长递增子序列的长度
            dp.append(i+1)
    return dp
        
# 正反各一遍
inc = lis(seq)
deq = lis(seq[::-1])[::-1]
# 去掉首位，因为序列中最大数的左右两边都要有递减序列，不能为空
print(n - max([inc[i]+deq[i]-1 for i in range(1,n-1)]))

Longest Increasing Subsequence（最长递增子序列）的O(nlogn)解法

发表于 2022-07-14 19:37:06 回复(0)

Python 3

liangzhengjie

不知道为啥超时了，是不是python太慢了

s_len = int(input())
s_arr = [int(i) for i in input().strip().split(' ')]

left_up = []
right_down = []

def countleftup(arr:list):
    longest = 0
    dp = [1 for i in range(len(arr))]
    for i,v1 in enumerate(arr, 0):
        for j,v2 in enumerate(arr[:i], 0):
            if v1 > v2:# can up
                dp[i] = max(dp[i], dp[j] + 1)
                longest = max(longest, dp[i])
    return dp

def countrightdown(arr:list):
    longest = 0
    dp = [1 for i in range(len(arr))]
    temp_index = [i for i in range(len(arr))]
    temp_index.reverse()
    for i in temp_index:# 一级索引为i
        for j,v in enumerate(arr[i + 1:], 0): # 二级索引为i + j，部分为：【i + 1:】
            if v < arr[i]:# 如果一级值大于二级值
                dp[i] = max(dp[i], dp[i + j + 1] + 1)
                longest = max(dp[i], longest)
    return dp

min_out = len(s_arr) - 1
left_up = countleftup(s_arr)
right_down = countrightdown(s_arr)
for i,v in enumerate(s_arr, 0):
    left_max = 0
    right_max = 0
    for j,v_left in enumerate(left_up[:i]):
        if s_arr[j] < v:
            left_max = max(left_max, v_left)
    for j,v_right in enumerate(right_down[i + 1:]):
        if s_arr[j] < v:
            right_max = max(right_max, v_right)
        
    out = len(s_arr) - left_max - right_max - 1
    min_out = min(min_out, out)
# print(left_up)
# print(right_down)
print(min_out)

发表于 2022-06-25 18:08:01 回复(0)

Python 3

牛客862164075号

def left_max(l):
    # 使用自己的长度1初始化dp数组
    # dp表示第i个人前面最大升序列的长度
    dp = [1] * len(l)
    for i in range(len(l)): # 遍历队列中的每一个人
        for j in range(i): # 遍历当前人前面的每一个人
            # 如果当前人前面的人比当前人高，并且当前人前面的最大升序列长度
            if l[j]<l[i] and dp[j]+1>dp[i]:
                dp[i]+=1
    return dp

while True:
    try:
        N = int(input())
        ss = list(map(int, input().split()))
        left_ss = left_max(ss)
        right_ss = left_max(ss[::-1])[::-1]
        sum_s = []
        for i in range(len(left_ss)):
            sum_s.append(left_ss[i]+right_ss[i]-1)
        print(str(N-max(sum_s)))
    except:
        break

大神“MIN大小姐”的题解非常有效。我来讲讲我对状态转移方程的认识。dp[i]状态数组表示在第i个人及其前面、满足升序列的最大长度。dp数组用1初始化，表示当前只考虑自己。状态转移方程if l[j]<l[i]表示前面的人比自己矮，dp[j]+1>dp[i]表示在当前人前面有和自己前面相同数量的最大升序列。因此if l[j]<l[i] and dp[j]+1>dp[i]表示当前人比之前的人高，并且当前人的前面的人有和当前人前面一样长度的上升序列。所以当前人的状态变为dp[i]+1

发表于 2022-06-25 10:06:36 回复(0)

Python 3

0x牛客

不知道 提交的时候为什么错，自测都对的。
n = int(input())
lst = []
while True:
    try:
        lst = list(map(int,input().split()))
        inc = []
        for i in range(len(lst)):
            tmp = []
            tmp.append(lst[i])
            flag = 0
            for j in range(i+1,len(lst)):
                if lst[j] > tmp[-1]:
                    tmp.append(lst[j])
                    flag = j
            if flag != 0:
                for j in range(flag,len(lst)):
                    if lst[j] < tmp[-1]:
                        tmp.append(lst[j])
            inc.append(tmp)
        inc.sort(key=len)
        print(len(inc[-1]))
    except:

发表于 2022-05-22 11:10:55 回复(0)

Python 3

HeartBeating

# 动态规划
def lengthOfLIS(lst):
    dp = []
    for i in range(len(lst)):
        dp.append(1)
        for j in range(i):
            if lst[i] > lst[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return dp # 每人左边可以站的人数

while True:
    try:
        n, heights = int(input()), list(map(int, input().split()))
        # dp1:每人左边可以站的人数，dp2:每人右边可以站的人数
        dp1, dp2 = lengthOfLIS(heights), lengthOfLIS(heights[::-1])[::-1]
        res = []
        for i in range(len(dp1)):
            res.append(dp1[i] + dp2[i] - 1)
        print(n-max(res))
    except:
        break

发表于 2022-05-09 16:12:16 回复(0)

Python 3

莫理

头大，python不用二分法可否

发表于 2022-05-08 19:24:13 回复(0)

Python 3

鱼説

def shenxu(l):
n=len(l) # 传入list的长度
dp=[1 for i in range(n)] #此列表将记录每个元素之前，算上他本身的升序元素总数
for i in range(n):
for j in range(i):
if l[j]<l[i] and dp[j]+1 > dp[i]:
dp[i]=dp[j]+1 #将求出开始到每个元素位置上最长升序的元素个数
return dp
while 1:
try:
a=int(input())
b=[int(i) for i in input().split()]
b1=b[::-1]
dp=shenxu(b) #求每个元素的左侧最长升序元素个数集合包含自己
dp1=shenxu(b1)[::-1] #求每个元素右侧最长降序的元素个数集合，包含自己
lst=[]
for j in range(a):
lst.append(dp[j]+dp1[j]-1) #升降计算中多算了一次自己减去
print(a-max(lst))
except:
break

发表于 2022-04-27 20:55:23 回复(0)

Python 3

牛客835424683号

N²超时？不理解，只要是小于1E8就可以的吧？

发表于 2022-04-07 19:41:32 回复(0)

Python 3

磨洋工匠人e

看半天没明白dp[i] = pos+1，这句其实没用

发表于 2022-03-12 13:15:23 回复(0)

Python 3

牛客693600570号

#最烦的莫过是代码写对了，自测运行都通过了，提交时没有输出，还不告诉你原因，不知道是什么原因，希望有哪位大佬给我看下
def dfx(b):
    c =[]
    d =[]
    for i, _ in enumerate(b):
        if c == []:
            c.append(_)
            d.append(len(c))
        else:
            if _ > max(c):
#                 print(_)
                c.append(_)
                d.append(len(c))
            else:
                for j, __ in enumerate(c):
                    if _ <=__ :
                        c[j] = _
                        d.append(len(c))
                        break
    return (c,d)

while True:
    try:
        a = input()
        b = list(map(int,input().split(" ")))
    except Exception as e:
#         print(e)
        break
    else:
        c1 = dfx(b)
        b.reverse()
        c2 = dfx(b)
        c2[1].reverse()
        for i, _ in enumerate(c1[1]):
            c1[1][i] = _ + c2[1][i]
        print(int(a)-max(c1[1]) +1)

发表于 2022-03-10 15:00:59 回复(0)

Python 3

牛客674896050号

while True:
    try:
        n = int(input())
        li1 = list(map(int, input().split(' ')))
        li2 = []
        for i in range(len(li1) - 1, -1, -1):
            li2.append(li1[i])


        def max_len(li):
            queue = []
            dp = [0] * len(li)
            for i in range(len(li)):
                if i == 0:
                    queue.append(li[0])
                    dp[0] = 0
                else:
                    if li[i] > queue[-1]:
                        queue.append(li[i])
                        dp[i] = len(queue) - 1
                    else:
                        for j in range(len(queue)):
                            if li[i] <= queue[0]:
                                dp[i] = 0
                                queue[0] = li[i]
                            else:
                                if li[i] <= queue[j] and li[i] > queue[j - 1]:
                                    dp[i] = j
                                    queue[j] = li[i]
            return dp


        q1 = max_len(li1)
        q2 = max_len(li2)
        q = []
        for i in range(n):
            q.append(q1[i] + q2[-(i + 1)] + 1)
        print(n - max(q))
    except:
        break

发表于 2022-03-02 11:21:14 回复(0)

Python 3

撒旦法说

while True:
    try:
        n = int(input())
        s = list(map(int,input().split()))
        
        lp=[0]*n
        lq=[0]*n
        for i in range(n):
            if i==0:
                lp[i]=0
            else:
                for j in range(i):
                    if s[i]>s[j]:
                        lp[i]=max(lp[i],lp[j]+1)
        s=s[::-1]
        for i in range(n):
            if i==0:
                lq[i]=0
            else:
                for j in range(i):
                    if s[i]>s[j]:
                        lq[i]=max(lq[i],lq[j]+1)
        lq=lq[::-1]
        re=[]
        for i in range(n):
            re.append(lp[i]+lq[i]+1)
        print(n-max(re))
    except:
        break

理论上应该这么算，就是Python容易超时

发表于 2021-12-16 20:54:18 回复(0)